package org.example.l0;

class Trie {
    Trie[] children = new Trie[26];
    private boolean isEnd;

    void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            node = getOrCreateChild(c, node);
        }
        node.isEnd = true;
    }

    boolean startsWith(String prefix) {
        Trie trie = searchNode(prefix);
        return trie != null;
    }

    boolean search(String word) {
        Trie trie = searchNode(word);
        return trie != null && trie.isEnd;
    }

    Trie searchNode(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            node = node.children[idx(c)];
            if (node == null) {
                return null;
            }
        }

        return node;
    }


    Trie getOrCreateChild(char c,
                          Trie node) {
        int idx = idx(c);
        Trie child = node.children[idx];
        if (child != null) {
            return child;
        }
        node.children[idx] = child = new Trie();
        return child;
    }

    int idx(char c) {
        return c - 'a';
    }
}